package org.example.dynamicprogram;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 力扣--动态规划
 * @Author chaigq
 * @Date 2020/11/26 下午11:52
 * @Version 1.0
 */
public class LeetCodeDynamicProgram {

    /**
     * 鸡蛋掉落问题
     *
     * 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
     *  每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
     *  你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
     *  每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
     *  你的目标是确切地知道 F 的值是多少。
     *  无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
     *
     *  示例 1：
     *  输入：K = 1, N = 2
     * 输出：2
     * 解释：
     * 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
     * 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
     * 如果它没碎，那么我们肯定知道 F = 2 。
     * 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
     *
     *  示例 2：
     *  输入：K = 2, N = 6
     * 输出：3
     *
     *  示例 3：
     *  输入：K = 3, N = 14
     * 输出：4
     *
     *  提示：
     *  1 <= K <= 100
     *  1 <= N <= 10000
     *
     *  Related Topics 数学 二分查找 动态规划
     */
    // 状态可以表示成 (K, N)，其中 K 为鸡蛋数，N 为楼层数。当我们从第 X 楼扔鸡蛋的时候：
    // 1、如果鸡蛋不碎，那么状态变成 (K, N-X)，即我们鸡蛋的数目不变，但答案只可能在上方的 N-X层楼了。
    // 也就是说，我们把原问题缩小成了一个规模为 (K, N-X) 的子问题；
    // 2、如果鸡蛋碎了，那么状态变成 (K-1, X-1)，即我们少了一个鸡蛋，但我们知道答案只可能在第 X 楼下方的 X-1 层楼中了。
    // 也就是说，我们把原问题缩小成了一个规模为 (K-1, X-1) 的子问题。

    //在上述的状态转移方程中，第一项 T1(X)=dp(K−1,X−1) 是一个随 X 的增加而单调递增的函数，
    //
    // 第二项 T2(X)=dp(K,N−X) 是一个随着 X 的增加而单调递减的函数
    //
    public int superEggDrop(int K, int N) {
        return superEggDropDfs(K, N);
    }
    // 存放记录
    Map<Integer, Integer> memo = new HashMap();
    private int superEggDropDfs(int K, int N) {

        if (! memo.containsKey(N * 1000 + K)){
            // 结果集
            int res;
            // N 层楼
            if (N == 0) res = 0;
            // 一个鸡蛋,N层楼，需要移动N次才能找到
            else if (K == 1) res = N;
            else {
                // 开始楼层为1层，结束楼层为N层
                int start = 1, end = N;
                // 采用二分法查找
                while (start + 1 < end){
                    // 中间值
                    int mid = (start + end) / 2;
                    // t1表示鸡蛋碎
                    int t1 = superEggDropDfs(K - 1, mid - 1);
                    // t2表示鸡蛋不碎
                    int t2 = superEggDropDfs(K, N - mid);
                    // 这里需要画图更清晰
                    if (t1 < t2) start = mid;
                    else if (t1 > t2) end = mid;
                    else start = end = mid;

                }
                res = 1 + Math.min(Math.max(superEggDropDfs(K - 1, start - 1), superEggDropDfs(K, N - start)),
                                   Math.max(superEggDropDfs(K - 1, end - 1), superEggDropDfs(K, N - end)));
            }
            memo.put(N * 1000 + K, res);
        }
        return memo.get(N * 1000 + K);
    }

    /**
     * 最大子矩阵
     * 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
     *  返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满
     * 足条件的子矩阵，返回任意一个均可。
     *  注意：本题相对书上原题稍作改动
     *
     *  示例：
     *  输入：
     * [
     *    [-1,0],
     *    [0,-1]
     * ]
     * 输出：[0,1,0,1]
     * 解释：输入中标粗的元素即为输出所表示的矩阵
     *
     *  说明：
     *  1 <= matrix.length, matrix[0].length <= 200
     *  Related Topics 动态规划
     */
    // 数组最大连续子序和
    public int maxSuArray(int[] array){
        int res = 0;
        // 结果集和，dp[i] 是array[i]结尾的子序和
        int[] dp = new int[array.length];
        dp[0] = 0;
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            res = Math.max(dp[i], res);
        }
        return res;
    }
    // 返回最大连续子数组的起始位置点坐标
    public int[] getMaxSuArray(int[] array){
        int res = 0;
        // 起始位置坐标
        int[] ans = new int[2];
        // 最大结果集合
        int[] dp = new int[array.length];
        dp[0] = array[0];
        // 坐标起始
        int start = 0;
        // 对于dp[i]=max(dp[i-1]+nums[i],nums[i]),两种情况都加了nums[i]，只是前面多加了dp[i-1]，所有很容易推出，当dp[i-1]<0时，后者大，反之前者大
        //
        for (int i = 1; i < array.length; i++) {
            if (dp[i - 1] > 0){
                // 还是处于连续序列中
                dp[i] = dp[i - 1] + array[i];
            }else {
                // 连续序列打断
                start = i;
                dp[i] = array[i];
            }
            if (dp[i] > res){
                res = dp[i];
                ans[0] = start;
                ans[1] = i;
            }
        }
        return ans;
    }

    public int[] getMaxMatrix(int[][] matrix) {
        // 当前问题需要延伸变换
        // 同样是再求最大子序和，我们需要将二维转化为一维，对于矩阵的每一列，我们将其加在一起，成为了一维上的一个数，二维矩阵的和转化为了一维数组的和
        // 存放结果集，左上角和右下角坐标集合
        int[] ans = new int[4];
        int row = matrix.length;
        int col = matrix[0].length;
        int[] b = new int[col];// 最大和矩阵，每一列的和，将二维合并成一维
        int sum = 0;
        int maxSum = Integer.MIN_VALUE; // 记录结果的最大值
        int beginR1 = 0;
        int beginC1 = 0; // 记录左上角初始坐标
        // 遍历每一行
        for (int i = 0; i < row; i++) {
            // 每次更换子矩形上边，就要清空b，重新计算每列的和
            // 将b数组中的值清空，设置为0
            Arrays.fill(b, 0);
            // 遍历i行
            for (int j = i; j < row; j++) {
                sum = 0; // 相当于dp值
                for (int k = 0; k < col; k++) {
                    // 这里变成了长度为col的一维数组
                    b[k] += matrix[j][k];
                    // 我们只是不断增加其高，也就是下移矩阵下边，所有这个矩阵每列的和只需要加上新加的那一行的元素
                    // 因为我们求dp[i]的时候只需要dp[i-1]和nums[i],所有在我们不断更新b数组时就可以求出当前位置的dp_i
                    if (sum > 0) sum += b[k];
                    else {
                        // 连续出现了中断
                        sum = b[k];
                        beginR1 = i;
                        beginC1 = k;
                    }
                    if (sum > maxSum){
                        maxSum = sum;
                        ans[0] = beginR1;
                        ans[1] = beginC1;
                        ans[2] = j;
                        ans[3] = k;
                    }
                }
            }
        }

        return ans;
    }

    /**
     * DI 序列的有效排列
     *
     * 我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。）
     * 有效排列 是对整数 {0, 1, ..., n} 的一个排列 P[0], P[1], ..., P[n]，使得对所有的 i：
     *
     *  如果 S[i] == 'D'，那么 P[i] > P[i+1]，以及；
     *  如果 S[i] == 'I'，那么 P[i] < P[i+1]。
     *
     *  有多少个有效排列？因为答案可能很大，所以请返回你的答案模 10^9 + 7.
     *
     *  示例：
     *  输入："DID"
     * 输出：5
     * 解释：
     * (0, 1, 2, 3) 的五个有效排列是：
     * (1, 0, 3, 2)
     * (2, 0, 3, 1)
     * (2, 1, 3, 0)
     * (3, 0, 2, 1)
     * (3, 1, 2, 0)
     *
     *  提示：
     *  1 <= S.length <= 200
     *  S 仅由集合 {'D', 'I'} 中的字符组成。
     *
     *  Related Topics 分治算法 动态规划
     */
    public int numPermsDISequence(String S) {
        // 我们用 dp(i, j) 表示确定了排列中到 P[i] 为止的前 i + 1 个元素，并且 P[i] 和未选择元素的相对大小为 j 的方案数（即未选择的元素中，有 j 个元素比 P[i] 小）。
        // 在状态转移时，dp(i, j) 会从 dp(i - 1, k) 转移而来，其中 k 代表了 P[i - 1] 的相对大小。如果 S[i - 1] 为 D，那么 k 不比 j 小；如果 S[i - 1] 为 I，那么 k 必须比 j 小。
        // TODO 动态转移方程：
        // dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp [ i - 1][ j + 1 ] + ... + dp[ i - 1][ i - 1 ]      if (S[ i - 1 ] == 'D')
        // dp[ i ][ j ] = dp[ i - 1 ][ j - 1] + dp [ i - 1][ j - 2 ] + ... + dp[ i - 1][ 0 ]       if (S[ i - 1 ]  == 'I')
        //
        // dp[i][j] 表示由范围 [0, i] 内的数字组成且最后一个数字为j的不同序列的个数
        // 当前为i-1时
        // if (S[i-1] == 'D') dp[i][j] += dp[i-1][k] ( j <= k <= i-1 )
        // else dp[i][j] += dp[i-1][k] ( 0 <= k < j )
        int mid = (int) 1e9 + 7;
        char[] chars = S.toCharArray();
        int[][] dp = new int[chars.length + 1][chars.length + 1];
        dp[0][0] = 1;
        // 遍历字符串长度
        for (int i = 1; i <= chars.length; i++) {
            // 【0，ℹi】内组成j的数
            for (int j = 0; j <= i; j++) {
                if (chars[i - 1] == 'D'){
                    // p[i-1] > p[i],k要大于j小于i
                    for (int k = j; k <= i - 1; k++) {
                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % mid;
                    }
                }else {
                    // p[i-1] < p[i]
                    for (int k = 0; k < j; k++) {
                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % mid;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= chars.length; i ++){
            res = (res + dp[chars.length][i]) % mid;
        }
        return res;
    }

    /**
     * 最长重复子数组
     *
     * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
     *
     *  示例：
     *  输入：
     * A: [1,2,3,2,1]
     * B: [3,2,1,4,7]
     * 输出：3
     * 解释：
     * 长度最长的公共子数组是 [3, 2, 1] 。
     *
     *  提示：
     *  1 <= len(A), len(B) <= 1000
     *  0 <= A[i], B[i] < 100
     *
     *  Related Topics 数组 哈希表 二分查找 动态规划
     */
    // 子序列默认不连续，子数组默认连续
    public int findLength(int[] A, int[] B) {
        if (A.length == 0 || B.length == 0) return 0;
        int res = 0;
        int[][] dp = new int[A.length + 1][B.length + 1];
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
















}
